package datastructure.stack;

/**
 * @author XY
 * @version 1.0
 * @date 2022/2/25 9:15
 * @Description
 */
public class Leet0206 {


    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }


    public static boolean isPalindrome(ListNode head) {
        if(head==null){
            return true;
        }
        //获取前半部分链表的尾节点
        ListNode pre = slowFast(head);
        //后半部分的头节点
        ListNode next = pre.next;
        //将后半部分链表反转，再与前半部分链表比较即可
        ListNode listNode = reverseList(next);
        ListNode root = head;
        ListNode root2 = listNode;
        while(root!=null&&root2!=null){
            if(root.val!=root2.val){
                return false;
            }
            root = root.next;
            root2 = root2.next;
        }
        return true;

    }

    private static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    public static ListNode slowFast(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null&&fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    public static void main(String[] args) {
        ListNode root = new ListNode(1);
        root.next=new ListNode(2);
        root.next.next=new ListNode(2);
        root.next.next.next=new ListNode(1);
        System.out.println(isPalindrome(root));
    }
}
